package dp

import "math"

// https://leetcode-cn.com/problems/delete-and-earn/
// 删除并获得点数
// 算法: 动态规划
// 公式: f[n] = max(numcount[n-1]*(n-1) + f[n-3], numcount[n]*n + f[n-2]) (公式有问题，待确认)
// 时间复杂度: O(n)
func DeleteAndEarn(nums []int) int {
	if 0 == len(nums) {
		return 0
	}

	// 初始化数组，以 数值 + 计数 为单位
	maxNumber := int(math.Pow(10, 4))
	numsCountArr := make([]int, maxNumber+1)
	for _, currentNum := range nums {
		numsCountArr[currentNum]++
	}

	maxPointArr := make([]int, maxNumber+1)

	maxPointArr[1] = numsCountArr[1]
	maxPointArr[2] = maxInt(numsCountArr[1], 2*numsCountArr[2])

	for index := 3; index <= maxNumber; index++ {
		if index < maxNumber {
			maxPointArr[index] = maxInt(numsCountArr[index-1]*(index-1)+maxPointArr[index-3], numsCountArr[index]*index+maxPointArr[index-2])
		} else {
			maxPointArr[index] = numsCountArr[index]*index + maxPointArr[index-2]
		}
	}

	return maxPointArr[maxNumber]
}

// func maxInt(a, b int) int {
// 	if a > b {
// 		return a
// 	}
// 	return b
// }
